题目
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example, [1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
标准回溯算法 \(O(n^n)\)
和无重复数字Permutations的区别在于，得先排序，然后跳过重复数字。比如[1,2,1]，先排序，得到[1,1,2]。然后递归遍历的时候处理过第一个1以后，跳过第二个1，直接处理2。
代码
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
List<Integer> buff = new ArrayList<>();
List<Integer> candidates = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
candidates.add(nums[i]);
}
backtracking(buff,candidates,result);
return result;
}
public void backtracking(List<Integer> buff, List<Integer> candidates, List<List<Integer>> result) {
if (candidates.size() == 0) { result.add(new ArrayList<Integer>(buff)); return; }
for (int i = 0; i < candidates.size(); i++) {
int temp = candidates.get(i);
buff.add(temp);
candidates.remove(i);
backtracking(buff,candidates,result);
candidates.add(i,temp);
buff.remove(buff.size()-1);
while (i+1 < candidates.size() && candidates.get(i+1).equals(candidates.get(i))) { i++; } // skip duplicates
}
}
}
结果
银弹！
